import java.util.*;
/**
 * 
 * 描述

给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 
0
<
n
≤
6
0<n≤6
要求：空间复杂度 
O
(
n
!
)
O(n!) ，时间复杂度 
O
(
n
!
）
O(n!）
 */
public class 没有重复项数字的全排列 {
    
    public static void main(String[] args) {
        
        int[] nums = new int[]{1,2,3};

        permute(nums);

        //输出打印结果
        for (List<Integer> permutation : permutations) {
            for (int num : permutation) {
                System.out.print(num+"  ");
            }
            System.out.println();
        }

    }

    //创建一个二维列表，赋全排列的值
    static ArrayList<ArrayList<Integer>> permutations = new ArrayList<>();
    //表示当前排列
    static ArrayList<Integer> current = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public static ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here

        //用于标记某数字是否使用过
        //boolean[] used = new boolean[nums.length];
        backtrack(num, current, permutations);

        return permutations;
    }

    //回溯算法
    private static void backtrack(int[] nums, ArrayList<Integer> current,
                                  ArrayList<ArrayList<Integer>> permutations) {
        //当前排列排满后 添加到总排列表中并该次递归
    	if (current.size() == nums.length) {
            permutations.add(new ArrayList<>(current));
            return;
        }
 
    	
        for (int i = 0; i < nums.length; i++) {
        	//当数字未被使用
            // if (!used[i]) {
            //     used[i] = true;	//标记为已使用
            //     current.add(nums[i]); //添加数字
                
            //     //继续搜索数字并添加。最后会添加
            //     backtrack(nums, current, permutations);  
                
 
            //     //回溯
            //     current.remove(current.size() - 1);  //移除这个数字
            //     //used[i] = false;  // 标记为未使用
            // }

            if(current.contains(nums[i])) continue;
            current.add(nums[i]); //添加数字
                
            //继续搜索数字并添加。最后会添加
            backtrack(nums, current, permutations);  
            //回溯
            current.remove(current.size() - 1);  //移除这个数字
        } 
    }
}
